/*
 * @lc app=leetcode.cn id=968 lang=javascript
 *
 * [968] 监控二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minCameraCover = function (root) {
  const helper = (root) => {
    if (root === null) {
      return {
        // 当前节点安装摄像头情况下的最小摄像头数量
        withCamer: Number.MAX_VALUE,
        // 当前节点被父节点覆盖情况下的最小摄像头数量
        noCamerWatchByParent: 0,
        // 当前节点被子节点覆盖情况下的最小摄像头数量
        noCarmerWachByChildren: 0,
      };
    }

    const left = helper(root.left);
    const right = helper(root.right);

    const withCamer =
      1 +
      Math.min(
        left.noCamerWatchByParent + right.noCamerWatchByParent,
        left.withCamer + right.noCamerWatchByParent,
        left.noCamerWatchByParent + right.withCamer
      );

    const noCamerWatchByParent = Math.min(
      left.noCarmerWachByChildren + right.noCarmerWachByChildren,
      left.withCamer + right.withCamer,
      left.withCamer + right.noCarmerWachByChildren,
      left.noCarmerWachByChildren + right.withCamer
    );

    const noCarmerWachByChildren = Math.min(
      left.withCamer + right.withCamer,
      left.withCamer + right.noCarmerWachByChildren,
      left.noCarmerWachByChildren + right.withCamer
    );

    return { withCamer, noCamerWatchByParent, noCarmerWachByChildren };
  };

  const result = helper(root);
  // (根节点有摄像头或根节点无摄像头但是被子节点覆盖)两种状态的最小值
  return Math.min(result.withCamer, result.noCarmerWachByChildren);
};
// @lc code=end
